package leetcode.od;

import org.junit.Test;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author pppppp
 * @date 2022/4/15 22:48
 * Catcher是MCA国的情报员，他工作时发现敌国会用一些对称的密码进行通信，
 * 比如像这些ABBA，ABA，A，123321，但是他们有时会在开始或结束时加入一些无关的字符以防止别国破解。
 * 比如进行下列变化 ABBA->12ABBA,ABA->ABAKK,123321->51233214　。因为截获的串太长了，
 * 而且存在多种可能的情况（abaaab可看作是aba,或baaab的加密形式），Cathcer的工作量实在是太大了，
 * 他只能向电脑高手求助，你能帮Catcher找出最长的有效密码串吗？
 * <p>
 * 输入描述：
 * 输入一个字符串（字符串的长度不超过2500）
 * <p>
 * 输出描述：
 * 返回有效密码串的最大长度
 * <p>
 * 示例1
 * 输入：ABBA
 * 输出： 4
 * <p>
 * 示例2
 * 输入： ABBBA
 * 输出： 5
 * <p>
 * 示例3
 * 输入：12HHHHA
 * 输出：4
 */
public class HJ32_密码截取 {
    @Test
    public void T_() {
        String[] s = {"ABBA", "ABBBA", "12HHHHA"};
        int[] ans = {4, 5, 4};
        for (int i = 0; i < s.length; i++) {
            System.out.println(maxHuiwen2(s[i]) == ans[i]);
        }

    }

    /*转化为查找最长回文字串的长度*/
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String s = scanner.nextLine();
            System.out.println(maxHuiwen(s));
        }
    }

    public static int maxHuiwen(String s) {
        char[] chs = s.toCharArray();
        int n = s.length(), max = 1;
        boolean[][] dp = new boolean[n][n];
        for (int i = n-1; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                if (chs[i] == chs[j]) {
                    if (j - i <= 2) {
                        dp[i][j] = true;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if (dp[i][j]) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        return max;
    }

    public static int maxHuiwen2(String s) {
        char[] chs = s.toCharArray();
        int n = s.length(), max = 1;
        boolean[][] dp = new boolean[n][n];
        for (boolean[] d : dp) {
            Arrays.fill(d,true);
        }
        for (int i = n-1; i >= 0; i--) {
            dp[i][i] = true;
            for (int j = i + 1; j < n; j++) {
                dp[i][j] = chs[i] == chs[j] && dp[i + 1][j - 1];
                if (dp[i][j]) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        return max;
    }
}
